% !TEX encoding = UTF-8 Unicode
\chapter*{Prefacio}
\addcontentsline{toc}{chapter}{Prefacio}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE,RO]{\bfseries\thepage}
\fancyhead[LO]{\bfseries Prefacio}
\fancyhead[RE]{\bfseries Prefacio}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
El interés principal de este trabajo es presentar algunos resultados de investigación en el área de Geometría Computacional, por lo que quizá debamos preguntarnos primero ¿Qué es la Geometría Computacional?

Desde un punto de vista general, la Geometría Computacional es un área dentro de las Ciencias de la Computación, en la cual los principales elementos de estudio son los objetos geométricos en un espacio dado, 
cabe resaltar que los espacios euclidianos son los más estudiados. 
Esta área surge como parte del diseño y análisis de algoritmos a finales de la década de 1970 y ha sido un área de creciente interés desde entonces, lo cual se ve reflejado en la consagración a nivel internacional de varias revistas en el área, así como en el crecimiento de la comunidad de investigadores activos.

El éxito de esta área de investigación puede ser explicado por la belleza tanto de los problemas que en ella se estudian, como de las soluciones obtenidas. Además, estos problemas no se quedan exclusivamente en la parte teórica, sino que trascienden gracias a sus diversas aplicaciones en áreas como graficación por computadora, sistemas de información geográfica (SIG), robótica, comunicación, redes, etc.
Es por esto que muchos de los problemas en Geometría Computacional son tangibles y tienden a tener una motivación real, lo que los hace fáciles de explicar aunque ciertamente no de resolver, como es el caso del siguiente problema.

Imaginemos que nos encontramos conduciendo nuestro auto en una calle y la alerta de gasolina nos avisa que necesitamos cargar el tanque urgentemente.
Sabemos que hay muchas gasolineras en la ciudad, pero dada nuestra urgencia queremos ir a la más cercana. 
Sería útil tener un mapa en el cual pudiéramos buscar dicha estación, un mapa en dónde la ciudad estuviera dividida en regiones y por cada región estuviera indicada la gasolinera más cercana: ver Figura~\ref{fig:VoronoiGasolineras}.
Esta subdivisión de la ciudad es llamada el diagrama de Voronoi del punto más cercano, 
y es uno de los conceptos fundamentales de la Geometría Computacional junto con todas sus variantes.

\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.85\textwidth]{img/intro/VoronoiGasolineras.pdf}
\caption{\small El diagrama de Voronoi del punto más cercano del conjunto de gasolineras de la ciudad.}
\label{fig:VoronoiGasolineras}
\end{center}
\end{figure}


\pagebreak
Pensemos ahora el problema de manera un poco distinta e imaginemos que dentro de la ciudad existe un conjunto de $m$ sitios en los que se pueden construir nuevas gasolineras. 
Sin embargo debido al presupuesto sólo $k$ de ellas se pueden construir.
Nos gustaría elegir los mejores $k$ sitios de construcción, de modo que la gente que se tiene que desplazar una mayor distancia para llegar a una gasolinera, no tenga que hacer un recorrido muy largo.
En pocas palabras, queremos minimizar la distancia máxima que existe entre un cliente y su gasolinera más cercana apegándonos al presupuesto.
La solución de dicho problema es estudiada en un área de la Geometría Computacional llamada \emph{Ubicación de Servicios}.
En general, este tipo de problemas son llamados problemas min-máx y serán abordados a lo largo de este trabajo.

Si pensamos que el presupuesto nos permite construir únicamente una gasolinera, entonces 
nos interesaría saber quién es el cliente más lejano a cada posible sitio de construcción, 
ya que sabiendo esto para cada sitio, podríamos elegir aquel en el que se minimice la distancia que recorre el cliente que se desplaza la mayor distancia.
Nuevamente nos gustaría tener una subdivisión del plano en regiones, de tal suerte que en cada región estuviera indicado cual es el cliente más lejano. De esta forma, si sabemos que una gasolinera pertenece a una de estas regiones, implícitamente sabríamos cual es su cliente más lejano y cual es la distancia que debe recorrer dicho cliente para utilizar este servicio.
A esta subdivisión del plano se le conoce como el diagrama de Voronoi del punto más lejano del conjunto de clientes y será el pilar principal del trabajo que presentaremos a continuación.

\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.95\textwidth]{img/intro/VoronoiClientes.pdf}
\caption{\small El diagrama de Voronoi del punto más lejano del conjunto clientes $\{c_1, \ldots, c_6\}$. La región del cliente $c_i$ está representada por el polígono $R(c_i)$, para toda $1\leq i\leq 6$.}
\label{fig:VoronoiGasolineras}
\end{center}
\end{figure}



